package com.bupt.leetcode;

import java.util.HashMap;

import com.sun.org.apache.xalan.internal.xsltc.runtime.Hashtable;

public class MathProblem {

    /**
     * 求平方根问题
     * 使用二分搜索
     * @param x
     * @return
     */
    public int sqrt(int x) {
        if( x <= 0){
        	return 0;
        }
        int left = 0,right = x;
        while (left <= right){
        	int mid = (left+right)/2;
        	if(mid * mid == x ){
        		return mid;
        	}else if(mid*mid > x ){
        		right = mid-1;
        	}else {
        		left = mid +1;
        	}
        }
        return left;
    }
    
	/**
	 * url : https://leetcode.com/problems/reverse-integer/
	 * 反转整数，判断溢出非常典型
	 * @param x
	 * @return
	 */
    public int reverse(int x) {
        if(x==Integer.MIN_VALUE)  
            return 0;  
        int num = Math.abs(x);  
        int res = 0;  
        while(num!=0){  
            if(res>(Integer.MAX_VALUE-num%10)/10)  
                return 0;  
            res = res*10+num%10;  
            num /= 10;  
        }  
        return x>0?res:-res;  
    }
    /**
     * happy数问题
     * @param n
     * @return
     */
    public boolean isHappy(int n) {
    	HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
    	int target = n;
    	while(!record.containsKey(target)){
    		int temp = 0,copy = target;
    		while(target > 0 ){
    			int b = target%10;
    			temp += b*b;
    			target/= 10;
    		}
    		if(temp == 1) return true;
    		target = temp;
    		record.put(copy,target);
    	}
    	return false;
    }
}
